// 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
// 通过，用例过大时超时
var myPow = function(x, n) {
    if (n == 0) { return 1 }

    function pow(n) {
        if (n <= 0) { return x }
        n--;
        return pow(n) * x
    }
    let sum = pow(Math.abs(n) - 1);
    console.log(sum)
    return n > 0 ? sum : 1 / sum;
};

// 使用二分法
var myPow = function(x, n) {
    if (n == 0) { return 1 }
    if (n < 0) {
        return 1 / myPow(x, -n);
    } //剪枝
    if (n % 2 == 1) { return x * myPow(x, n - 1) } //当无法二分时，先减一，再乘x，保持值相等的前提下继续二分
    // 二分n,每次折半，增加效率
    return myPow(x * x, n / 2)
};